package Hot_100;

import java.util.Arrays;
import java.util.Scanner;

//打家劫舍
public class Hot_100_198 {
    /**
     * 主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //初始化数组
        int n = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //调用处理函数并输出结果
        System.out.println(rob(arr));
    }

    // 备忘录
    private static int[] memo;

    /**
     * 求最高金额
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        // 初始化备忘录
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        // 强盗从第 0 间房子开始抢劫
        return dp(nums, 0);
    }

    // 返回 dp[start..] 能抢到的最大值

    /**
     * dp
     *
     * @param nums
     * @param start
     * @return
     */
    private static int dp(int[] nums, int start) {
        if (start >= nums.length) {
            return 0;
        }
        // 避免重复计算
        if (memo[start] != -1) return memo[start];

        int res = Math.max(dp(nums, start + 1),
                nums[start] + dp(nums, start + 2));
        // 记入备忘录
        memo[start] = res;
        return res;
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)